#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 
# Copyright (c) 2017 Baidu.com, Inc. All Rights Reserved
# 

"""
File: shell_sort.py
Author: zhangyang(zhangyang40@baidu.com)
Date: 2017/10/30 15:57
"""


def shellSort(list):
    gap = len(list) // 2
    # gap = 1
    while gap > 0:
        for i in range(gap, len(list)):
            var = list[i]
            j = i
            while j >= gap and list[j - gap] > var:
                list[j] = list[j - gap]
                j -= gap
            list[j] = var
        gap //= 2
        # print gap


if __name__ == '__main__':
    list2sort = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
    shellSort(list2sort)
    print list2sort
